package com.shm.leetcode;

/**
 * 59. 螺旋矩阵 II
 * 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：n = 3
 * 输出：[[1,2,3],[8,9,4],[7,6,5]]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：[[1]]
 *
 *
 * 提示：
 *
 * 1 <= n <= 20
 * @author SHM
 */
public class GenerateMatrix {
    public int[][] generateMatrix(int n) {
        int[][] dir = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
        int dirIndex = 0;
        int[][] ans = new int[n][n];
//        boolean[][] vis = new boolean[n][n];
        int row = 0,col =0;
        for(int i=1;i<=n*n;i++){
            ans[row][col]=i;
//            vis[row][col]=true;
            int row1 = row+dir[dirIndex][0],col1=col+dir[dirIndex][1];
//            if(row1<0||row1>=n||col1<0||col1>=n||vis[row1][col1]){
            if(row1<0||row1>=n||col1<0||col1>=n||ans[row1][col1]!=0){
                dirIndex = (dirIndex+1)%4;
            }
            row = row+dir[dirIndex][0];
            col = col+dir[dirIndex][1];
        }
        return ans;
    }

    /**
     * 方法二：按层模拟
     * 可以将矩阵看成若干层，首先填入矩阵最外层的元素，其次填入矩阵次外层的元素，直到填入矩阵最内层的元素。
     *
     * 定义矩阵的第 kk 层是到最近边界距离为 kk 的所有顶点。例如，下图矩阵最外层元素都是第 11 层，次外层元素都是第 22 层，最内层元素都是第 33 层。
     *
     *
     * [[1, 1, 1, 1, 1, 1],
     *  [1, 2, 2, 2, 2, 1],
     *  [1, 2, 3, 3, 2, 1],
     *  [1, 2, 3, 3, 2, 1],
     *  [1, 2, 2, 2, 2, 1],
     *  [1, 1, 1, 1, 1, 1]]
     * 对于每层，从左上方开始以顺时针的顺序填入所有元素。假设当前层的左上角位于 (\textit{top}, \textit{left})(top,left)，右下角位于 (\textit{bottom}, \textit{right})(bottom,right)，按照如下顺序填入当前层的元素。
     *
     * 从左到右填入上侧元素，依次为 (\textit{top}, \textit{left})(top,left) 到 (\textit{top}, \textit{right})(top,right)。
     *
     * 从上到下填入右侧元素，依次为 (\textit{top} + 1, \textit{right})(top+1,right) 到 (\textit{bottom}, \textit{right})(bottom,right)。
     *
     * 如果 \textit{left} < \textit{right}left<right 且 \textit{top} < \textit{bottom}top<bottom，则从右到左填入下侧元素，依次为 (\textit{bottom}, \textit{right} - 1)(bottom,right−1) 到 (\textit{bottom}, \textit{left} + 1)(bottom,left+1)，以及从下到上填入左侧元素，依次为 (\textit{bottom}, \textit{left})(bottom,left) 到 (\textit{top} + 1, \textit{left})(top+1,left)。
     *
     * 填完当前层的元素之后，将 \textit{left}left 和 \textit{top}top 分别增加 11，将 \textit{right}right 和 \textit{bottom}bottom 分别减少 11，进入下一层继续填入元素，直到填完所有元素为止。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/spiral-matrix-ii/solution/luo-xuan-ju-zhen-ii-by-leetcode-solution-f7fp/
     * @param n
     * @return
     */
    public int[][] generateMatrix_2(int n) {
        int[][] res = new int[n][n];
        int up = 0, down = n - 1, left = 0, right = n - 1, index = 1;
        while(index <= n * n){
            for(int i = left; i <= right; i++){
                res[up][i] = index++;
            }
            up++;
            for(int i = up; i <= down; i++){
                res[i][right] = index++;
            }
            right--;
            for(int i = right; i >= left; i--){
                res[down][i] = index++;
            }
            down--;
            for(int i = down; i >= up; i--){
                res[i][left] = index++;
            }
            left++;
        }
        return res;
    }
}
